{-
	Kernelization Module
	
	r51
	
	29 March 2010
	
	Daniel De Guzman
	
	This module is part of the FPT Algorithm Implementation Project for the Massey University
	paper: 159.402 Programming Languages. It contains functions that primarily deal with
	the Kernelization Phase.
	
	The algorithm returns the new k, graph and vertex cover. The kernelization rules are as 
	follows:
		Rule #1 Delete any isolated vertex from the graph
		Rule #2 Remove any vertex with degree 1 from the graph
		Rule #3 Add any vertex that is greater than the parameter k.
				
	It must be noted that the algorithm is applied recursively until there is no longer any 
	graph entry that meets the criteria.  Also, each time a vertex is added to the vertex 
	cover, the parameter k is reduced by one and all occurrences of the vertices are removed 
	from the graph.
-}

module Kernelization where

import Datatypes
import Graph

-- |=========================================================================================|
-- |								 Kernelization Functions								 |
-- |=========================================================================================|

-- Loop Kernelization process until a graph cannot be kernelized anymore
--	Checks for k. If k is zero, there is no point.
--	Compares the size of the vertices of the kernelized graph to the size of the vertices
--	of the normal graph
loopKernelization :: ProcessGraph -> Kgraph
loopKernelization (k, g1, g2, vc)
	= if (((read k) > 0) && (graphSize kernedGraph /= graphSize g2)) 
		then loopKernelization (kernedK, kernedGraph, kernedGraph, kernedVC)
		else (kernedK, kernedGraph,kernedVC)
			where
				kernedK :: K
				kernedK = getKernelizedK kernelizedGraph
				
				kernedGraph :: Graph
				kernedGraph = getKernelizedGraph kernelizedGraph
				
				kernelizedGraph :: Kgraph
				kernelizedGraph = kernelize (k, g1, g2, vc)
				
				kernedVC :: VertexCover
				kernedVC = getKernelizedVC kernelizedGraph
				
				graphSize :: Graph -> Int
				graphSize g = length(getAllVertices (unzipGraph g))

-- Main Kernelization Function
--	Checks for each rule before processing them accordingly
--	Does not do anything if the criteria is not met.
kernelize :: ProcessGraph -> Kgraph
kernelize (k, [], graph, vCover) = (k, graph, vCover)
kernelize (k, (x:xs), graph, vCover)
	= if isRuleOne x
		then kernelize $ processRuleOne (k, (x:xs), graph, vCover) 
		else if isRuleTwo x
		then kernelize $ processRuleTwo (k, (x:xs), graph, vCover)
		else if isRuleThree k x
		then kernelize $ processRuleThree (k, (x:xs), graph, vCover)
		else kernelize (k, xs, graph, vCover)

-- Processes a Graph according to the first rule:
--	Removes vertex from the graph
processRuleOne :: ProcessGraph -> ProcessGraph
processRuleOne (k, (x:xs), graph, vCover) 
	= (k, xs, removeVertexFromGraph, vCover)
		where
			removeVertexFromGraph = removeVertex x graph

-- Processes a Graph according to the seoond rule:
--	Decrements K if added to the vertex cover
--	Removes vertex of degree 1 from the graph
--	Adds neighbour to the cover
--	Removes all occurrences of vertex added into the cover from the graph
processRuleTwo :: ProcessGraph -> ProcessGraph
processRuleTwo (k, (x:xs), graph, vCover) 
	=  (decrementIfNotInCover, xs, removeAllOccurrences, addNeighbourToCover)
			where 
				decrementIfNotInCover = decrementK k (head (getNeighbours x)) vCover
				removeAllOccurrences = removeFromNeighboursList (head (getNeighbours x)) removeNeighbourFromVList
				removeNeighbourFromVList = removeVertex (head (getNeighbours x),[]) removeVertexFromGraph
				removeVertexFromGraph = removeVertex x graph
				addNeighbourToCover = addToCover (head (getNeighbours x)) vCover

-- Processes a Graph according to the third rule:
--	Decrements K if added to the vertex cover
--	Removes vertex greater than k from the graph
--	Removes all occurences of vertex added to cover from the graph
--	Adds vertex removed to the cover
processRuleThree :: ProcessGraph -> ProcessGraph
processRuleThree (k, (x:xs), graph, vCover) 
	=  (decrementIfNotInCover, xs, removeAllOccurrences, addVertexToCover)
			where
				decrementIfNotInCover = decrementK k (getVertexLabel x) vCover
				removeAllOccurrences = removeFromNeighboursList (getVertexLabel x) removeVertexFromGraph
				removeVertexFromGraph = removeVertex x graph
				addVertexToCover = addToCover (getVertexLabel x) vCover
-- |-----------------------------------------------------------------------------------------|

-- |=========================================================================================|
-- |								Kernelization Subfunctions								 |
-- |=========================================================================================|

-- Acquire K
getKernelizedK :: Kgraph -> K
getKernelizedK (k, g, vc) = k

-- Acquire Graph
getKernelizedGraph :: Kgraph -> Graph
getKernelizedGraph (k, g, vc) = g

-- Acquire Vertex Cover
getKernelizedVC :: Kgraph -> VertexCover
getKernelizedVC (k, g, vc) = vc

-- Adds a vertex to the vertex cover if it is not already in it
addToCover :: Vertex -> VertexCover -> VertexCover
addToCover v vc
	| elem v vc = vc
	| otherwise = v:vc

-- Decrements the parameter k if the vertex is not in the vertex cover
decrementK :: K -> Vertex -> VertexCover -> String
decrementK k v vc
	| elem v vc = k
	| otherwise = show ((read k) - 1)

-- Removes a vertex from a graph entry's neighbour list
removeFromNeighboursList :: Vertex -> Graph -> Graph
removeFromNeighboursList _ [] = []
removeFromNeighboursList v (x:xs)
	= if isInNeighbours v (getNeighbours x)
		then (getVertexLabel x, newNeighbours) : removeFromNeighboursList v xs
		else x : removeFromNeighboursList v xs
			where
				newNeighbours = removeFromNeighbours v (getNeighbours x)

-- Removes a vertex from a neighbour's list
removeFromNeighbours :: Vertex -> Neighbours -> Neighbours
removeFromNeighbours v [] = []
removeFromNeighbours v (x:xs)
	= if (v == x)
		then removeFromNeighbours v xs
		else x : removeFromNeighbours v xs

-- Removes a vertex from a graph
removeVertex :: GraphEntry -> Graph -> Graph
removeVertex e [] = []
removeVertex e (x:xs)
	= if (getVertexLabel e == getVertexLabel x)
		then removeVertex e xs
		else x : removeVertex e xs
-- |-----------------------------------------------------------------------------------------|

-- |=========================================================================================|
-- |									Boolean Functions									 |
-- |=========================================================================================|

-- Checks if a vertex is one of the neighbours
isInNeighbours :: Vertex -> Neighbours -> Bool
isInNeighbours _ [] = False
isInNeighbours v (x:xs)
	= if (v == x)
		then True
		else isInNeighbours v xs

-- Checks if a graph entry fulfills the first rule's criteria
isRuleOne :: GraphEntry -> Bool
isRuleOne entry 
	= if (length (getNeighbours entry) == 0)
		then True
		else False


-- Checks if a graph entry fulfills the second rule's criteria
isRuleTwo :: GraphEntry -> Bool
isRuleTwo entry 
	= if (length (getNeighbours entry) == 1)
		then True
		else False

-- Checks if a graph entry fulfills the third rule's criteria
isRuleThree :: K -> GraphEntry -> Bool
isRuleThree k entry 
	= if (length (getNeighbours entry) > read k)
		then True
		else False

-- |-----------------------------------------------------------------------------------------|
-- |=========================================================================================|